// File: ms_lock_free_queue.hpp
#pragma once

#include <atomic>

namespace Common {

  /**
   * @brief 基于 Michael & Scott 算法的无界多生产者多消费者无锁队列。
   *
   *  - 模板参数 @tparam T 指定队列中元素类型。
   *  - 内部使用带哨兵节点的单向链表，通过原子 CAS 操作同步 head 与 tail 指针。
   *  - 每次入队追加新节点，出队时将旧哨兵节点挂入退休链表，生命周期结束后再统一回收。
   *
   * ⚠️ 设计注意：
   *  - 本示例采用“延迟回收”来避免并发释放造成的悬空指针问题，仅适合演示或受控场景。
   *  - 若需长期运行，应结合 Hazard Pointer / Epoch GC / RCU 等机制做安全内存回收。
   */
  template<typename T>
  class MSLockFreeQueue final {
  public:
    using value_type = T;

    MSLockFreeQueue() {
      Node *dummy = new Node();
      head_.store(dummy, std::memory_order_relaxed);
      tail_.store(dummy, std::memory_order_relaxed);
    }

    ~MSLockFreeQueue() {
      // 释放仍在队列链表中的节点
      Node *node = head_.load(std::memory_order_relaxed);
      while (node != nullptr) {
        Node *next = node->next.load(std::memory_order_relaxed);
        delete node;
        node = next;
      }

      // 释放已经退休但尚未归还的节点
      Node *retired = retired_head_.load(std::memory_order_relaxed);
      while (retired != nullptr) {
        Node *next = retired->retire_next;
        delete retired;
        retired = next;
      }
    }

    /**
     * @brief 入队操作：在链表尾部追加新节点。
     *
     * @param value 待入队的元素（以常量引用接收，保持通用性）。
     * @note
     *  - 采用 compare_exchange_weak 循环实现无锁入队。
     *  - 成功链接新节点后，再尝试推进 tail 指针。
     */
    void enqueue(const T &value) {
      Node *new_node = new Node(value);
      while (true) {
        Node *tail = tail_.load(std::memory_order_acquire);
        Node *next = tail->next.load(std::memory_order_acquire);
        if (tail == tail_.load(std::memory_order_acquire)) {
          if (next == nullptr) {
            if (tail->next.compare_exchange_weak(next,
                                                 new_node,
                                                 std::memory_order_release,
                                                 std::memory_order_relaxed)) {
              tail_.compare_exchange_strong(tail,
                                            new_node,
                                            std::memory_order_release,
                                            std::memory_order_relaxed);
              return;
            }
          } else {
            tail_.compare_exchange_strong(tail,
                                          next,
                                          std::memory_order_release,
                                          std::memory_order_relaxed);
          }
        }
      }
    }

    /**
     * @brief 出队操作：从链表头部提取元素。
     *
     * @param out_value 若成功出队，写入此引用。
     * @return 若成功返回 true；若队列为空返回 false。
     * @note head 指针始终指向当前哨兵节点，真正的数据存于 head->next。
     */
    bool dequeue(T &out_value) {
      while (true) {
        Node *head = head_.load(std::memory_order_acquire);
        Node *tail = tail_.load(std::memory_order_acquire);
        Node *next = head->next.load(std::memory_order_acquire);

        if (head == head_.load(std::memory_order_acquire)) {
          if (head == tail) {
            if (next == nullptr) {
              return false; // 队列为空
            }
            tail_.compare_exchange_strong(tail,
                                          next,
                                          std::memory_order_release,
                                          std::memory_order_relaxed);
          } else {
            out_value = next->value;
            if (head_.compare_exchange_strong(head,
                                              next,
                                              std::memory_order_release,
                                              std::memory_order_relaxed)) {
              retireNode(head); // 延迟回收旧哨兵节点
              return true;
            }
          }
        }
      }
    }

  private:
    struct Node {
      T value{};
      std::atomic<Node *> next{nullptr};
      Node *retire_next{nullptr}; ///< 退休链表指针（仅在出队后访问）
      Node() = default;
      explicit Node(const T &v) : value(v) {}
    };

    void retireNode(Node *node) noexcept {
      Node *retired_head = retired_head_.load(std::memory_order_relaxed);
      do {
        node->retire_next = retired_head;
      } while (!retired_head_.compare_exchange_weak(retired_head,
                                                    node,
                                                    std::memory_order_release,
                                                    std::memory_order_relaxed));
    }

    std::atomic<Node *> head_{nullptr};          ///< 哨兵节点指针（出队逻辑从 head->next 开始）
    std::atomic<Node *> tail_{nullptr};          ///< 尾节点指针（入队逻辑在 tail->next 上推进）
    std::atomic<Node *> retired_head_{nullptr};  ///< 已退休待回收节点的无锁链表头
  };

} // namespace Common